package hotLeetcode;

import javax.sound.midi.Soundbank;
import java.util.ArrayList;
import java.util.List;

public class H207Leetcode {
    public boolean canFinish(int numCourses, int[][] prerequisites) {



        //构建图
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        //填充图
        for (int[] prereq  : prerequisites) {
            graph.get(prereq[0]).add(prereq[1]);
        }

        //状态数组 ： 0：未访问 1：正在访问 2：已访问
        int[] visited = new int[numCourses];

        //遍历所有课程进行 DFS
        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0) {
                if (hasCycle(i, graph, visited)) {
                    return false;
                }
            }
        }


        return true;


    }

    private boolean hasCycle(int course ,List<List<Integer>> graph, int[] visited) {
        // 课程正在被访问中，说明有环
        if (visited[course] == 1) {
            return true;
        }


        // 课程已经访问过了，说明无环
        if (visited[course] == 2) {
            return false;
        }

        // 标记课程为正在访问
        visited[course] = 1;

        // 递归访问所有邻接课程
        for (int nextCourse : graph.get(course)) {
            if (hasCycle(nextCourse, graph, visited)) {
                return true;
            }
        }

        // 标记课程访问完成
        visited[course] = 2;

        return false;
    }

    public static void main(String[] args) {
        int numCourses = 2;
        int[][] prerequisites = {{1, 0}, {0, 1}};

        H207Leetcode h207Leetcode = new H207Leetcode();
        System.out.println(h207Leetcode.canFinish(numCourses, prerequisites));
    }
}
